Generally described, computing devices can be utilized to display images to computer users on a display screen. To generate various images, the typical computer display is made up of a grid of equal-sized blocks generally referred to as pixels. For example, a display screen may be made up of a grid of 1024 pixels in width and 820 pixels in height. To generate color images on the display, each pixel within the display screen can be individually controlled by a computer such that each pixel can be given a unique color. Accordingly, one skilled in the relevant art will appreciate that the resolution of displayed color images depends greatly on the number of pixels in the display screen and the palette of colors available for each pixel.
In one common embodiment, a pixel color is achieved by combining red, green and blue characteristics to generate a particular color. More specifically, each pixel is assigned a particular red value, green value and blue value, which are generated by the display screen to form a resulting color for the pixel. The specification of the three-color value is typically referred to as the red, green and blue value, or RGB value, of the pixel. One skilled in the relevant art will appreciate that the number of potential red, green and blue values for a pixel is dependent entirely on the amount of data utilized to specify the data. For example, if 8-bits are used to represent each color value in a binary representation (e.g., 8-bit red value, 8-bit green value, and 8-bit blue value), there would be would be 28, or 256, possibilities for each color value. Based on an 8-bit representation, there would be more than 16 million possible RGB combinations (256 red×256 green×256 blue). Accordingly, screen display color resolution benefit greatly, in terms of total possible colors, from representing pixel color attributes utilizing at least 8 bits per color value.
Although representing pixel color attributes utilizing 8-bits per color value results in improved color, there are a number of environments in which limited data transfer bandwidth may effect the ability to specify the full range of possible colors. For example, in a communication network environment, such as the Internet, the performance of data delivery, such as the delivery of a Web page, is optimized by limiting the amount of data transmitted over network. Further, there are a number of environments in which image storage and rendering is optimized by limiting the size of the image file. In an environment utilizing 8-bit RGB values, the transfer and/or storage of 24-bits of data per pixel results in more than 20 million bits of data per page of display for a 1024 by 820 pixel display screen. Accordingly, there is an emphasis to improve computer performance by approximating color data for each pixel with a lesser amount of data while mitigating the potential color degradation associated with the lesser data. For example, the ability to represent the RGB value with 8 total bits instead of 24 total bits could reduce the amount of data transferred by a factor of three.
One attempt to approximate 24-bit RGB pixel color values relates to mapping of a subset of the 24-bit color representations into a selective color palette that will be applied to individual pixels. For example, if the selective color palette is limited to a selective 256 total colors, each pixel's color values can be approximated by only 8 bits. In some embodiments, the 256 colors are preselected to cover a wide range of possible color values. Although the preselected color palette approach is easy to implement and does not require an approximation of each individual color display, one skilled in the relevant art will appreciate the selection of the 256 most applicable colors from 16 million possible colors can vary greatly for each display. Accordingly, a pre-selected 256-color palette approximation yields potentially unsatisfactory results in some displays. For example, in a color display utilizing a number of shades of particular color, a pre-selected color palette would likely not be able to yield adequate results.
Another embodiment related to generating a selective color palette relates to the a dynamic selection of a selective color palette corresponding to the frequency of the appearance of colors within a particular display, referred to generally as an optimized color palette. An optimized color palette allows pixel color to be represented from a lesser amount of data (e.g., 8-bits), while allowing the selection of the color palette to correspond more closely to the colors appearing in a display. One well-known method for optimizing a color palette utilizing octree is referred to generally as the Gervautz and Purgthofer octree method. Although the Gervautz and Purgthofer method will be described generally below, one skilled in the relevant art will have a detailed understanding of the method.
Generally described, the Gervautz and Purgthofer method corresponds to graphing each pixel's RGB color values into a hierarchical tree structure. In an 8-bit RGB model, each pixel's RGB color value is mapped into hierarchically structure that includes a number of hierarchically arranged 8-bit arrays, or octree arrays. Each level of the octree represents a 3-bit index corresponding to the merging of a bit from red, green and blue color values. For example, the first 3-bit index value corresponds to the merging of the most significant bits of the red, green and blue colors. Each octree array element corresponds to a potential value of the three-bit index. Furthermore, each octree array element keeps a running total of the number of pixels that match the array elements designated value and a cumulative RGB value of each matching pixel. Although the hierarchical structure may include as many levels as there are bits in the data being mapped (e.g., 8 levels for 8-bit color representation), one skilled in the relevant art will appreciate that a lesser number of levels may be used and that the least significant bits may be ignored altogether.
Starting with a base octree array corresponding to the most significant RGB pixel color values, each octree array element can link to another level octree array representing the next most least significant bit in the RGB color value. Accordingly, the base octree array can link to eight different second level octree arrays. Similarly, each of the eight-second level octree arrays can link to eight third level arrays for a total of 64 octree arrays. Once all of bits of the RGB value are mapped, or a lesser number of bits are selected to be mapped, the set of octree arrays in the lowest level are considered the leaf nodes of the octree and represent each of the unique colors found within the display. One skilled in the art will appreciate that each array element to the base octree array, corresponding to the most significant bits of the RGB values, define distinctive color branches of the octree. Each successive octree array is representative of different shades of a color branch associated with the octree. Accordingly, the differences between the lowest octree arrays represent more refined shades of the color branches.
FIG. 1 is a block diagram illustrative of a mapping of a pixel RGB value into a hierarchical tree structure in accordance with the Gervautz and Purgthofer method. Table 100 represents a single pixel's 8-bit RGB value denoted by rows 102, 104, and 106 respectively. Row 108 corresponds to a three-digit combination of each bit place of the RGB value, with the most significant bit on the left.
In accordance with the Gervautz and Purgthofer method, each bit place value in row 108 corresponds to the value tracked within a hierarchical octree from most significant bit to least significant bit, respectively. As illustrated in FIG. 1, because the most significant bit value in row 108 corresponds to the binary representation of the numeral “3,” the value of the array element in octree array 110 is incremented by one. Similarly, because the second most significant bit value in row 108 corresponds to the binary representation of the number “6,” the array element in octree array 112 is incremented by one. Note that array element 112 is linked to the previous tracked array element in array 110. For purposes of illustration, octree arrays 114, 116 and 118 are populated according to the next three most significant bits of row 108. Accordingly, the array elements of array element 118 (on the fifth level) are considered the leaf nodes of the octree. However, one skilled in the relevant art will understand that three additional octree arrays could be populated (now shown).
In accordance with the Gervautz and Purgthofer method, the generation of the optimized color palette corresponds to a mapping of the unique colors in the color octree to the palette. In the simplest embodiment, if the number of leaf nodes does not exceed, or matches, the number of colors available in the color palette, each of the unique colors represented by the leaf node is mapped to the color palette and the method terminates. However, in many embodiments, the number of unique colors exceeds the number of available colors in the palette and the number of unique colors must be reduced. In accordance with the Gervautz and Purgthofer method, to reduce the number of leaf nodes, one or more leaf nodes are merged up one level within the same parent node. The merger results in the parent node becoming the new leaf node and reduces the number of overall leaf nodes in the color octree. This process is generally referred to as trimming or pruning. The trimming continues until the number the leaf nodes equals the number of available colors in the optimized color palette.
In accordance with the Gervautz and Purgthofer method, the selection of which leaf nodes to trim relates to reducing the leaf nodes containing the fewest pixel counts. More specifically, the method identifies which leaf node octree array elements is tracking the lowest number of pixels and merges the leaf node octree array with the closest proximate octree array element having a common parent node. The merger results in a higher-level octree array becoming the leaf node and including pixel information for the two merged arrays corresponding to an average of the pixel information. The process continues merging the lowest pixel count leaf nodes until the number of octree leaf nodes is reduced to the target number of leaf nodes.
FIG. 2 is a block diagram illustrative of an octree 200 that has been mapped in accordance with the Gervautz and Purgthofer method. The octree can include a number of levels of octree arrays, including octree arrays 202, 204 and 206, in which octree array 206 corresponds to a leaf node array. Octree array 206 includes a third array element 208 that includes pixel tracking information 212 of 2 pixels and the cumulative RGB information for the two pixels. Likewise, the octree array 206 includes a seventh array element 210 that includes pixel tracking information 214 of 1 pixel with it cumulative RGB information. Assuming that the pixel array element 210 is the lowest leaf node within the octree, in accordance with the Gervautz and Purgthofer method, array element 208 and array element 210 are merged up one level to form a new leaf node including all the pixel information.
FIG. 3 is a block diagram of the octree 200 of FIG. 2 illustrating the resulting merger of two array elements. As illustrated in FIG. 3, array elements 208 and 210 of array 206 have been merged into array element 216 of array 204. Accordingly, array element 216 becomes a new leaf node of the octree and includes pixel-tracking information 218 corresponding to the cumulative RGB values of the previously merged array elements. The pixel tracking information 218 is then utilized to generate an averaged RGB values for the pixels previously found in each array.
Although the Gervautz and Purgthofer method provides a manner in which to optimize a selective color palette according to the colors found in particular display, the method can yield unsatisfactory results if applied to displays utilizing a greater number of pixels of one primary color and fewer pixels of another primary colors. For example, assume a display corresponds to a large number of pixels predominantly correspond to various shades of red. Further, assume that a limited number of pixels that corresponds to a single shade of yellow. Clearly, the limited yellow pixels would be important as contrast to the number of other red pixels. However, in accordance with the Gervautz and Purgthofer method, the leaf node representative of yellow would be trimmed and eventually merged with the red pixel color branches because the yellow leaf nodes would have a relatively low pixel tracking count. Accordingly, the optimized color palette would not include the appropriate shade of yellow and the contrast of the display would be lost. Accordingly, an approximation of the display would be inadequate.
Thus, there is a need for a color palette optimization method that preserves distinctive colors during the optimization process.